package com.wuxuan.algorithm_homework.treeNode;

import org.junit.jupiter.api.Test;

import java.util.List;

/**
 * 二叉搜索树
 * 二叉搜索树是一种高效的 二叉树数据结构，它满足以下性质:
 * 1.有序性:对于任意节点，其 左子树的所有节点值 < 当前节点值 < 右子树的所有节点值
 * 2.递归结构:左右子树也分别是二叉搜索树。
 * <p>
 * 验证二叉搜索树
 * BST的核心操作:
 * 查找(Search)
 * 插入(Insert)
 * 删除(Delete)
 */
public class BinarySearchTree {

    /**
     * 验证二叉搜索树
     * <p>
     * 判断一棵二叉树是否为二叉搜索树，假设二叉树节点的值为任意整数
     *
     * 时间复杂度:O(n),假设n是二叉树节点的个数
     * 空间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBSTHelper(TreeNode root, long lower, long upper) {
        if (root == null) {
            return true;
        }

        if (root.val <= lower || root.val >= upper) {
            return false;
        }

        return isValidBSTHelper(root.left, lower, root.val) && isValidBSTHelper(root.right, root.val, upper);

    }

    @Test
    public void testIsValidBST() {
//        自创一个二叉树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        System.out.println(isValidBST(root));

    }


    /**
     * 查找(Search)
     *
     * 时间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     * 空间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     * @param root
     * @param target
     * @return
     */
    public boolean search(TreeNode root, int target) {
        if (root == null) {
            return false;
        }

        if (root.val == target) {
            return true;
        } else if (root.val > target) {
            return search(root.left, target);
        } else {
            return search(root.right, target);
        }
    }

    @Test
    public void testSearch() {
//        自创一个二叉树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        System.out.println(search(root, 5));
        System.out.println(search(root, 6));
        System.out.println(search(root, 10));
    }

    /**
     * 插入(Insert)
     *
     * 时间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     * 空间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     * @param root
     * @param key
     * @return
     */
    public TreeNode insert(TreeNode root, int key) {
        if (root == null) {
            return new TreeNode(key);
        }

        if (root.val > key) {
            root.left = insert(root.left, key);
        } else if (root.val < key) {
            root.right = insert(root.right, key);
        }

        return root;
    }

    @Test
    public void testInsert() {
//        自创一个二叉树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

//        TreeNode root2 = insert(root, 10);
        TreeNode root2 = insert(root, 7);

        TreeNodeDemo treeNodeDemo = new TreeNodeDemo();
        List<List<Integer>> result = treeNodeDemo.levelOrder(root2);
        System.out.println(result);
    }

    /**
     * 删除(Delete)
     *
     * 时间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     * 空间复杂度:O(h),假设h是树的高度。完全二叉树:O(logn)。最坏情况:O(n),所有的节点连成一排
     * @param root
     * @param key
     * @return
     */
    public TreeNode delete(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (root.val > key) {
            root.left = delete(root.left, key);
        } else if (root.val < key) {
            root.right = delete(root.right, key);
        } else {
            //找到key的节点,节点的位置有三种情况
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            //节点既有左子树又有右子树
            //将当前节点的值替换为右子树的最小值
            TreeNode minNode = findMinNode(root.right);
            root.val = minNode.val;
            //删除右子树中的minNode
            root.right = delete(root.right, minNode.val);
        }
        return root;
    }

    private TreeNode findMinNode(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        //root.left == null,此时当前root即为最小值
        return root;
    }

    @Test
    public void testDelete() {
//        自创一个二叉树
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        TreeNode root2 = delete(root, 3);

        TreeNodeDemo treeNodeDemo = new TreeNodeDemo();
        List<List<Integer>> result = treeNodeDemo.levelOrder(root2);
        System.out.println(result);
    }
}
